package com.ydc.ln.tutorial.algorithm;

import java.util.Stack;

import org.junit.Test;

/**
 * 迷宫求解
 * 
 * @author ydc
 * 
 */
public class MazeTest {
	int BLOCK = 1; // 1代表障碍物
	int ACCESS = 2; // 2代表通路
	int ACCESS_PASS = 3; // 3代表已走过的通路

	int EAST = 1;
	int SOUTH = 2;
	int WEST = 3;
	int NORTH = 4;

	// 地图
	int[][] map = new int[][] { { BLOCK, BLOCK, BLOCK, BLOCK, BLOCK, BLOCK, BLOCK, BLOCK, BLOCK, BLOCK }, { BLOCK, ACCESS, ACCESS, BLOCK, ACCESS, ACCESS, ACCESS, BLOCK, ACCESS, BLOCK },
			{ BLOCK, ACCESS, ACCESS, BLOCK, ACCESS, ACCESS, ACCESS, BLOCK, ACCESS, BLOCK }, { BLOCK, ACCESS, ACCESS, ACCESS, ACCESS, BLOCK, BLOCK, ACCESS, ACCESS, BLOCK },
			{ BLOCK, ACCESS, BLOCK, BLOCK, BLOCK, BLOCK, BLOCK, ACCESS, ACCESS, BLOCK }, { BLOCK, ACCESS, ACCESS, ACCESS, BLOCK, ACCESS, ACCESS, ACCESS, ACCESS, BLOCK },
			{ BLOCK, ACCESS, BLOCK, ACCESS, ACCESS, ACCESS, BLOCK, ACCESS, ACCESS, BLOCK }, { BLOCK, ACCESS, BLOCK, BLOCK, BLOCK, ACCESS, BLOCK, BLOCK, ACCESS, BLOCK },
			{ BLOCK, BLOCK, ACCESS, ACCESS, ACCESS, ACCESS, ACCESS, ACCESS, ACCESS, BLOCK }, { BLOCK, BLOCK, BLOCK, BLOCK, BLOCK, BLOCK, BLOCK, BLOCK, BLOCK, BLOCK } };

	@Test
	public void testMap() {
		printMap(map);
	}

	@Test
	public void testMazePath() {
		// printMap(map);
		PosType start = new PosType(1, 1);
		PosType end = new PosType(8, 8);
		mazePath(map, start, end);
	}

	public void mazePath(int[][] map, PosType start, PosType end) {
		Stack<SElemType> stack = new Stack<SElemType>();
		SElemType elem = new SElemType();
		elem.setOrd(1);
		elem.setSeat(start);
		stack.push(elem);
		map[elem.getSeat().getX()][elem.getSeat().getY()]++;
		int count_map = 0;
		printMap(map);
		System.out.println("---------------" + (++count_map));

		do {
			SElemType cur = stack.peek();
			int isPass = 0;
			int di = cur.getDi();

			do {
				di = (di < 4) ? ++di : di;
				if (getMapStatus(cur.getSeat(), di) == ACCESS) {
					if (cur.getSeat().equals(end)) {
						System.out.println("OK");
						return;
					}
					isPass = 1;

					SElemType next = new SElemType();
					next.setOrd(cur.getOrd() + 1);
					next.setSeat(getPosType(cur.getSeat(), di));
					stack.push(next);
					map[next.getSeat().getX()][next.getSeat().getY()]++;

					printMap(map);
					System.out.println("---------------" + (++count_map));
				}
				if (isPass == 0 && di == NORTH) {
					stack.pop();
					break;
				}
			} while (isPass == 0);
			cur.setDi(di);
		} while (!stack.empty());
	}

	// 返回该点的东南西北方向的通路情况
	public int getMapStatus(PosType pos, int di) {
		int x = pos.getX();
		int y = pos.getY();
		if (di == EAST) {
			y++;
		} else if (di == SOUTH) {
			x++;
		} else if (di == WEST) {
			y--;
		} else if (di == NORTH) {
			x--;
		}
		return map[x][y];
	}

	public PosType getPosType(PosType pos, int di) {
		int x = pos.getX();
		int y = pos.getY();
		if (di == EAST) {
			y++;
		} else if (di == SOUTH) {
			x++;
		} else if (di == WEST) {
			y--;
		} else if (di == NORTH) {
			x--;
		}
		return new PosType(x, y);
	}

	// 打印地图
	public void printMap(int[][] map) {
		for (int[] i : map) {
			for (int j : i) {
				char c = '#';
				switch (j) {
				case 1:
					c = '#';
					break;
				case 2:
					c = '2';
					break;
				case 3:
					c = '3';
					break;
				default:
					break;
				}
				System.out.print(c);
			}
			System.out.println();
		}
	}
}

// 每一步的记录
class SElemType {
	private int ord;
	private PosType seat;
	// 方向默认为0
	private int di = 0;

	public int getOrd() {
		return ord;
	}

	public void setOrd(int ord) {
		this.ord = ord;
	}

	public PosType getSeat() {
		return seat;
	}

	public void setSeat(PosType seat) {
		this.seat = seat;
	}

	public int getDi() {
		return di;
	}

	public void setDi(int di) {
		this.di = di;
	}
}

// 位置类
class PosType {
	private int x;
	private int y;

	public PosType() {
	}

	public PosType(int x, int y) {
		this.x = x;
		this.y = y;
	}

	@Override
	public boolean equals(Object obj) {
		boolean flag = false;
		if (obj instanceof PosType) {
			PosType other = (PosType) obj;
			if (this.getX() == other.getX() && this.getY() == other.getY()) {
				flag = true;
			}
		}
		return flag;
	}

	public int getX() {
		return x;
	}

	public void setX(int x) {
		this.x = x;
	}

	public int getY() {
		return y;
	}

	public void setY(int y) {
		this.y = y;
	}

}
